In the context of network computing, network virtualization can be implemented to combine computing networks, hardware and software network resources and network functionality into a single, software-based administrative entity. A service provider can use network virtualization to provide one or more Virtual Networks (VNs) to its customers. Each VN provides network services for transmitting data packets between a source node and a destination node in the customer's network. Examples of network services can include connectivity, encryption, data storage and manipulations, and application-level services. The VN can be implemented using computing resources in the service provider's network, including for example, one or more computing nodes. By using network virtualization, these computing resources can be shared among different VNs. In some cases, a VN can be a Virtual Private Network (VPN), which provides security functions over the VN. The VPN can be implemented using secure tunnels that are protected by encryptions, authentications, or a combination thereof.